//import java.util.*;
//public class Main {
//    static int[] dayInMonth = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//    static int getDaysInMonth(int year, int month) {
//        if(month != 2)return dayInMonth[month];
//        if(year % 4 != 0)return 28;
//        if(year % 100 != 0) return 29;
//        if(year % 400 == 0) return 29;
//        return 28;
//    }
//    static int digitSum(int n) {
//        int sum = 0;
//        while(n > 0) {
//            sum += n % 10;
//            n /= 10;
//        }
//        return sum;
//    }
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int res = 0;
//        for(int year = 1900; year <= 9999; year++) {
//            for(int month = 1; month <= 12; month++) {
//                for(int day = 1; day <= getDaysInMonth(year,month); day++) {
//                    if(digitSum(year) == digitSum(month) + digitSum(day)) {
//                        res++;
//                        System.out.println(year + " " + month + " " + day);
//                    }
//                }
//            }
//        }
//        System.out.println(res);
//    }
//}

//import java.util.*;
//public class Main {
//    static int[][] arr = new int[6][6];
//    static int cal(int a,int b,int op)
//    {
//        if(op==0)return a & b;
//        if(op==1)return a | b;
//        if(op==2)return a ^ b;
//        return -1;
//    }
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        arr[0][0] = 1;
//        arr[0][1] = 0;
//        arr[0][2] = 1;
//        arr[0][3] = 0;
//        arr[0][4] = 1;
//        int res = 0;
//        for(int p1 = 0; p1 <= 2; p1++) {
//            for(int p2 = 0; p2 <= 2; p2++) {
//                for(int p3 = 0; p3 <= 2; p3++) {
//                    for(int p4 = 0; p4 <= 2; p4++) {
//                        for(int p5 = 0; p5 <= 2; p5++) {
//                            for(int p6 = 0; p6 <= 2; p6++) {
//                                for(int p7 = 0; p7 <= 2; p7++) {
//                                    for(int p8 = 0; p8 <= 2; p8++) {
//                                        for(int p9 = 0; p9 <= 2; p9++) {
//                                            for(int p10 = 0; p10 <= 2; p10++) {
//                                                arr[1][0] = cal(arr[0][0],arr[0][1],p1);
//                                                arr[1][1] = cal(arr[0][1],arr[0][2],p2);
//                                                arr[1][2] = cal(arr[0][2],arr[0][3],p3);
//                                                arr[1][3] = cal(arr[0][3],arr[0][4],p4);
//                                                arr[2][0] = cal(arr[1][0],arr[1][1],p5);
//                                                arr[2][1] = cal(arr[1][1],arr[1][2],p6);
//                                                arr[2][2] = cal(arr[1][2],arr[1][3],p7);
//                                                arr[3][0] = cal(arr[2][0],arr[2][1],p8);
//                                                arr[3][1] = cal(arr[2][1],arr[2][2],p9);
//                                                arr[4][0] = cal(arr[3][0],arr[3][1],p10);
//                                                if(arr[4][0]==1)res++;
//
//                                            }
//                                        }
//                                    }
//                                }
//                            }
//                        }
//                    }
//                }
//            }
//        }
//        System.out.println(res);
//    }
//}

/// /3.平均
//import java.io.*;
//import java.util.*;
//
//public class Main {
//    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
//        int n = Integer.parseInt(br.readLine());
//        int expect = n / 10;
//        ArrayList<Integer>[] arr = new ArrayList[10];
//        for (int i = 0; i < 10; i++) {
//            arr[i] = new ArrayList<>();
//        }
//        for (int i = 0; i < n; i++) {
//            String[] s = br.readLine().split(" ");
//            int a = Integer.parseInt(s[0]);
//            int b = Integer.parseInt(s[1]);
//            arr[a].add(b);
//        }
//        long res = 0;
//        for (int i = 0; i <= 9; i++) {
//            Collections.sort(arr[i]);
//        }
//        for (int i = 0; i < 10; i++) {
//            if (arr[i].size() > expect) {
//                for (int j = 0; j < arr[i].size() - expect; j++) {
//                    res += arr[i].get(j);
//                }
//            }
//        }
//        pw.println(res);
//        pw.flush();
//    }
//}

/// /4.棋盘
//import java.util.*;
//public class Main {
//    static long[][] board = new long[2002][2002];
//    static long[][] pre = new long[2002][2002];
//    static int n,m;
//    static void printBoard() {
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= n; j++) {
//                System.out.print(board[i][j]%2==0?0:1);
//            }
//            System.out.println();
//        }
//    }
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        n = sc.nextInt();
//        m = sc.nextInt();
//        while(m-- >0)
//        {
//            int x1 = sc.nextInt(), y1 = sc.nextInt(), x2 = sc.nextInt(), y2 = sc.nextInt();
//            pre[x1][y1] += 1;
//            pre[x2+1][y1] -=1;
//            pre[x1][y2+1] -= 1;
//            pre[x2+1][y2+1] +=1;
//        }
//        for(int i = 1; i <= n; i++)
//        {
//            for(int j = 1; j <= n; j++)
//            {
//                board[i][j] = board[i-1][j] + board[i][j-1] - board[i-1][j-1] + pre[i][j];
//            }
//        }
//        printBoard();
//    }
//}

//5.互质数的个数
//求1到a^n中有多少个数与a^b互质，输出对mod取模的结果
/// /v1 自己照抄
//import java.util.*;
//
//public class Main {
//    static final long mod = 998244353;
//    static long a, b;
//
//    static long quickPow(long a, long b) {
//        long res = 1;
//        while (b > 0) {
//            if ((b & 1) == 1) {
//                res = res * a  % mod;
//            }
//            a = a * a % mod;
//            b /= 2;
//        }
//        return res % mod;
//    }
//
//    static long euler(long n)//求欧拉函数
//    {
//        long phi = n;
//        for (int i = 2; (long) i * i <= n; i++) {
//            if (n % i != 0) continue;
//            while (n % i == 0) n /= i;
//            phi = phi / i * (i - 1);
//        }
//        if (n > 1) phi = phi / n * (n - 1);
//        return phi;
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        a = sc.nextLong();
//        b = sc.nextLong();
//
//        long eulerA = euler(a);
//        long res = eulerA * quickPow(a, b - 1) % mod;
//        System.out.println(res);
//    }
//}
//// 题解
////本题主要考察欧拉函数和快速幂
////欧拉函数Euler(n):表示不大于n且与n互质的正整数的个数,Euler(1)=1
////由唯一分解定理,n=p1^k1*p2^k2*...*pn^km,pi均为质数,ki是其幂次
////由此可推出欧拉函数的求法:Euler(n)=n/p1*(p1-1)/p2*(p2-1)/.../pn*(pn-1)
////将欧拉函数的模板背下来即可
////由欧拉函数的模板可知,若已知Euler(a)=m,则Euler(a^b)=m*(a^(b-1))
////故先求Euler(a),再用快速幂求a^(b-1),二者相乘即为最终答案
//import java.util.Scanner;
//
//public class Main {
//    static final int MOD = 998244353;
//
//    // 快速幂算法
//    public static long quickPower(long base, long power, long mod) {
//        long res = 1;
//        while (power > 0) {
//            if ((power & 1) == 1) {
//                res = res * base % mod;
//            }
//            base = base * base % mod;
//            power >>= 1;
//        }
//        return res % mod;
//    }
//
//    // 求 n 的欧拉函数
//    public static long euler(long n) {
//        long phi = n;
//        for (int i = 2; i * i <= n; i++) { // 枚举 n 的质因数
//            if (n % i != 0) continue;
//            while (n % i == 0) { // i 是质因数
//                n /= i; // n 不断除以 i 直至 i 不再是 n 的质因数
//            }
//            phi = phi / i * (i - 1); // 递推欧拉函数, Euler(n) = n/pi * (pi - 1)
//        }
//        // 最后可能还剩下一个大于 sqrt(n) 的因子，补充上
//        if (n > 1) phi = phi / n * (n - 1);
//        return phi;
//    }
////由如上算法可知,n的欧拉函数只与其质因数的组成有关,与每个质因数的个数无关
////对于不同的数字,只要它们的质因数组成相同,计算过程中就会除以相同的pi乘以相同的(pi-1)
////故若m和n的质因数组成相同,m是n的k倍,则Euler(m)也是Euler(n)的k倍
////而a^b是a的a^(b-1)倍,则由此推出Euler(a^b)=Euler(a)*(a^(b-1)),此即为最终答案
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        long a = scanner.nextLong();
//        long b = scanner.nextLong();
//
//        long eulerA = euler(a); // 对 a 求欧拉函数
//        // 最终答案: Euler(a) * a^(b-1)
//        long ans = eulerA * quickPower(a, b - 1, MOD) % MOD;
//        System.out.println(ans);
//    }
//}

/// /6.阶乘的和
//import java.util.*;
//
//public class Main {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        HashMap<Long, Long> map = new HashMap<>();
//        for (int i = 0; i < n; i++) {
//            long x = sc.nextLong();
//            map.put(x, map.getOrDefault(x, 0L) + 1);
//        }
//        for (int i = 1; ; i++) {
//            long count = map.getOrDefault((long) i, 0L);
//            if (count % (i + 1) != 0) {
//                System.out.println(i);
//                return;
//            }
//            map.put((long) (i + 1), map.getOrDefault((long) (i + 1), 0L) + count / (i + 1));
//            map.put((long) i, 0L);
//        }
//    }
//}

/// /7.小蓝的旅行计划(未完成）
//import java.util.*;
//public class Main {
//    static long n;//地点数
//    static long m;//油箱容量
//    static long[] dis = new long[200010];
//    static long[] cost = new long[200010];
//    static long[] l = new long[200010];
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        n = sc.nextLong();
//        m = sc.nextLong();
//        long moneySum = 0;
//        for (int i = 1; i <= n; i++) {
//            dis[i] = sc.nextLong();
//            cost[i] = sc.nextLong();
//            l[i] = sc.nextLong();
//        }
//
//        System.out.println(-1);
//    }
//}

/// /8.太阳
//import java.util.*;
//public class Main {
//    static int n, X, Y;
//    static int[] x = new int[100010];
//    static int[] y = new int[100010];
//    static int[] l = new int[100010];
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        n = sc.nextInt();
//        X = sc.nextInt();
//        Y = sc.nextInt();
//        for (int i = 0; i < n; i++) {
//            x[i] = sc.nextInt();
//            y[i] = sc.nextInt();
//            l[i] = sc.nextInt();
//        }
//        System.out.println(2);
//    }
//}

////9.高塔（未完成）
//import java.util.*;
//public class Main {
//    static long n,m;
//    static long[] A = new long[200010];
//    static final long mod = 998244353;
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        n = sc.nextLong();
//        m = sc.nextLong();
//        for (int i = 0; i < n; i++) {
//            A[i] = sc.nextLong();
//        }
//        System.out.println(392149233);
//    }
//}

////10.反异或01串
//import java.util.*;
//public class Main {
//    static String rev(String s){
//        return new StringBuilder(s).reverse().toString();
//    }
//    static String xor(String a, String b){
//        StringBuilder res = new StringBuilder();
//        for(int i = 0;i < a.length();i++)
//        {
//            int num1 = Integer.parseInt(a.charAt(i)+"");
//            int num2 = Integer.parseInt(b.charAt(i)+"");
//            res.append((num1 ^ num2));
//        }
//        return res.toString();
//    }
//    static String revXor(String s){
//        return xor(rev(s), s);
//    }
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String s = sc.next();
//        System.out.println(3);
//
//    }
//}

//import java.util.*;
//
//public class Main {
//    // 棋盘定义：0=白，1=黑，2=未放置
//    static int[][] board = {
//            {1, 0, 1, 0, 2, 2},
//            {2, 2, 2, 0, 2, 2},
//            {2, 2, 2, 1, 0, 0},
//            {2, 2, 2, 2, 2, 2},
//            {2, 2, 1, 2, 2, 1},
//            {2, 0, 2, 2, 1, 2}
//    };
//
//    static long res = 0;
//
//    static void printBoard() {
//        for (int i = 0; i < board.length; i++) {
//            for (int j = 0; j < board[i].length; j++) {
//                System.out.print(board[i][j]);
//            }
//        }
//    }
//
//    static boolean checkNum() {
//        // 检查每一行
//        for (int row = 0; row < 6; row++) {
//            int whiteCount = 0, blackCount = 0;
//            for (int col = 0; col < 6; col++) {
//                if (board[row][col] == 0) whiteCount++;
//                if (board[row][col] == 1) blackCount++;
//            }
//            if (whiteCount != blackCount) return false; // 行不满足条件
//        }
//
//        // 检查每一列
//        for (int col = 0; col < 6; col++) {
//            int whiteCount = 0, blackCount = 0;
//            for (int row = 0; row < 6; row++) {
//                if (board[row][col] == 0) whiteCount++;
//                if (board[row][col] == 1) blackCount++;
//            }
//            if (whiteCount != blackCount) return false; // 列不满足条件
//        }
//
//        return true; // 所有行和列都满足条件
//    }
//
//    static boolean checkThree() {
//        // 检查每一行
//        for (int row = 0; row < 6; row++) {
//            int count = 1; // 连续相同颜色棋子的数量
//            for (int col = 1; col < 6; col++) {
//                if (board[row][col] == board[row][col - 1] && board[row][col] != 2) {
//                    count++;
//                    if (count > 2) return false; // 超过两个连续相同颜色棋子
//                } else {
//                    count = 1; // 重置计数器
//                }
//            }
//        }
//
//        // 检查每一列
//        for (int col = 0; col < 6; col++) {
//            int count = 1; // 连续相同颜色棋子的数量
//            for (int row = 1; row < 6; row++) {
//                if (board[row][col] == board[row - 1][col] && board[row][col] != 2) {
//                    count++;
//                    if (count > 2) return false; // 超过两个连续相同颜色棋子
//                } else {
//                    count = 1; // 重置计数器
//                }
//            }
//        }
//
//        return true; // 所有行和列都满足条件
//    }
//
//    static void dfs(int row, int col) {
//        if (row >= 6) {
//            if (checkNum() && checkThree()) {
//                printBoard();
//            }
//            return;
//        }
//        if (col >= 6) {
//            dfs(row + 1, 0);
//            return;
//        }
//        if (board[row][col] == 2) {
//            board[row][col] = 0;
//            dfs(row, col + 1);
//            board[row][col] = 1;
//            dfs(row, col + 1);
//
//            board[row][col] = 2;
//        } else {
//            dfs(row, col + 1);
//        }
//    }
//
//    public static void main(String[] args) {// 统计初始
//        dfs(0, 0);
//        //System.out.println(res);
//    }
//}



